import java.util.Arrays;

public class TestHeap {
    private int[]elem;
    private int usedSize;

    public int getUsedSize() {
        return usedSize;
    }

    public int[] getElem() {
        return elem;
    }

    public void creatArray(int[]arr){
        this.elem= Arrays.copyOf(arr,arr.length);
        usedSize=arr.length;
    }

    /*
    建堆
     */
    public void createHeap(){
        //把所有具有左或右孩子根结点进行向下调整
        for (int parent = (this.usedSize-1-1)/2; parent >=0 ; parent--) {
            adjust(parent);
        }
    }
    /*
    向下调整
     */
    private void adjust(int parent){
        //左孩子
        int child=(parent*2)+1;
        while (child<usedSize){
            //前提是有右孩子
            if(child+1<usedSize&&elem[child]<elem[child+1]){
                child++;//让右孩子和根结点交换
            }
            //此时拿到的肯定是左右孩子中最大的元素
            if(elem[child]>elem[parent]){
                //交换 传入数组
                swap(elem,child,parent);
                //开始向下移动，因为改变了其他树的根结点
                parent=child;
                child=parent*2+1;
            }else{
                //如果不大于根结点，就不需要交换了
                break;
            }
        }
    }
    /*
    交换
     */
    private void swap(int[]arr,int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
    /*
    扩容
     */
    public boolean isFull(){
        if(usedSize>=elem.length){
            return true;
        }
        return false;
    }
    /*
    插入元素  向上调整
     */
    public void shiftUp(int child) {
        if(isFull()){
            elem=Arrays.copyOf(elem,elem.length*2);
        }
        int tmp=usedSize;//插入的数据下标
        elem[tmp]=child;//放入元素
        while (tmp>0){
            //每一次进入给parent重新赋值
            int parent=(tmp-1)/2;
            if(elem[tmp]>elem[parent]){
                swap(elem,tmp,parent);
                //交换后给tmp重新赋值
                tmp=parent;
            }else{
                break;
            }
        }
        usedSize++;
    }
    /*
    堆的删除 删除堆顶
     */
    public int delete(){
        //为空返回-1
        if(usedSize==0)return -1;
        //返回删除的值
        int old=elem[usedSize-1];
       //互换
        swap(elem,0,usedSize-1);
        //删除
        this.usedSize--;
        //向下调整
        adjust(0);
        return old;
    }
}
